
//990. 等式方程的可满足性

class Solution {
    public boolean equationsPossible(String[] equations) {
        int length = equations.length;
        char[] parent = new char[26];
        //并查集，先把每个节点的父亲设置为自己，在查找最远祖先的时候发现父亲是自己的时候就停止
        for (int i = 0; i < 26; i++) {
            parent[i] = (char)('a'+i);
        }
        //开始遍历数组创建并查集
        for(String s: equations){
            char a = s.charAt(0);
            char b = s.charAt(3);
            if(s.charAt(1)=='='){
                union(parent,a,b);
            }
        }
        //开始判断不等于是否和等于矛盾
        for(String s: equations){
            char a = s.charAt(0);
            char b = s.charAt(3);
            if(s.charAt(1)=='!'){
                char pa = find(parent,a);
                char pb = find(parent,b);
                if(pa==pb)return false;
            }
        }
        return true;
    }

    //查找某个节点的祖先
    public char find(char[] p ,char t){
        char tmp_p = t;
        while (p[tmp_p-'a']!=tmp_p){
            tmp_p = p[tmp_p-'a'];
        }
        return tmp_p;
    }

    //将两个节点合并，通过找到祖先再合并
    public void union (char[] p ,char a,char b){
        char pa = find(p,a);
        char pb = find(p,b);
        p[pa-'a'] = pb;
    }
}

